package com.mashibing.class11;

// 本题测试链接：letcode 431 https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree

import java.util.ArrayList;
import java.util.List;

/**
 * 将多叉树转化为原来二叉树;
 * 且将二叉树转化为原来的多叉树.
 *
 */
public class Code03_EncodeNaryTreeToBinaryTree {
    // 提交时不要提交这个类
    public static class Node {
        public int val;
        public List<Node> children; // 它的孩子是一个列表.

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    // 提交时不要提交这个类
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 只提交这个类即可
    class Codec {
        // Encodes an n-ary tree to a binary tree.
        // 多叉树 转化为 二叉树.(TreeNode : 二叉树  Node : 多叉树)
        // 将 多叉树的任意节点的子节点集合 都放在 该节点的左树的右边界上.
        public TreeNode encode(Node root) {
            if (root == null) {
                return null;
            }
            // 多叉树的头结点值 也就是 二叉树的头结点值
            TreeNode head = new TreeNode(root.val);
            // root节点的所有子节点的集合 全部往当前节点的左子树中挂载.
            // root的子节点集合 构成了一颗子树, 挂载在该节点的左子树上.
            head.left = en(root.children);
            return head;
        }

        private TreeNode en(List<Node> children) {
            TreeNode head = null;
            TreeNode cur = null;
            for (Node child : children) {
                // 建立当前孩子的节点.
                TreeNode tNode = new TreeNode(child.val);
                if (head == null) {  // 遍历多叉树的第一个子节点的时候, head 为 null.
                    head = tNode; // 蒋多叉树的第一个子节点赋值给head.
                } else {
                    cur.right = tNode; // head不为空, 当前节点设置为 cur的右节点.
                }
                cur = tNode;   // 当前节点移动到 tNode节点处.
                cur.left = en(child.children);// 当前节点的子节点 递归调用en函数, 蒋当前节点的子节点集合挂载在当前节点的左子树中.
            }
            return head;
        }

        // Decodes your binary tree to an n-ary tree.
        // 二叉树 转化为 多叉树. (TreeNode: 二叉树; Node: 多叉树)
        public Node decode(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 左树的右孩子.
            return new Node(root.val, de(root.left));
        }

        public List<Node> de(TreeNode root) {
            List<Node> children = new ArrayList<Node>();
            // 不断遍历当前节点的右节点,将其节点依次插入children孩子集合当中 并将其返回.
            while (root != null) {
                // root 是长兄.
                Node cur = new Node(root.val, de(root.left));
                children.add(cur);
                root = root.right;
            }
            return children;
        }
    }
}
